{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Distance Between a Pair of Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下标对中的最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>非递增</strong> 的整数数组 <code>nums1</code>​​​​​​ 和 <code>nums2</code>​​​​​​ ，数组下标均 <strong>从 0 开始</strong> 计数。</p>\n",
    "\n",
    "<p>下标对 <code>(i, j)</code> 中 <code>0 &lt;= i &lt; nums1.length</code> 且 <code>0 &lt;= j &lt; nums2.length</code> 。如果该下标对同时满足 <code>i &lt;= j</code> 且 <code>nums1[i] &lt;= nums2[j]</code> ，则称之为 <strong>有效</strong> 下标对，该下标对的 <strong>距离</strong> 为 <code>j - i</code>​​ 。​​</p>\n",
    "\n",
    "<p>返回所有 <strong>有效</strong> 下标对<em> </em><code>(i, j)</code><em> </em>中的 <strong>最大距离</strong> 。如果不存在有效下标对，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>一个数组 <code>arr</code> ，如果每个 <code>1 &lt;= i &lt; arr.length</code> 均有 <code>arr[i-1] &gt;= arr[i]</code> 成立，那么该数组是一个 <strong>非递增</strong> 数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。\n",
    "最大距离是 2 ，对应下标对 (2,4) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,2,2], nums2 = [10,10,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>有效下标对是 (0,0), (0,1) 和 (1,1) 。\n",
    "最大距离是 1 ，对应下标对 (0,1) 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。\n",
    "最大距离是 2 ，对应下标对 (2,4) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums1</code> 和 <code>nums2</code> 都是 <strong>非递增</strong> 数组</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-distance-between-a-pair-of-values](https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-distance-between-a-pair-of-values](https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[55,30,5,4,2]\\n[100,20,10,10,5]', '[2,2,2]\\n[10,10,1]', '[30,29,19,5]\\n[25,25,25,25,25]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1,n2 = len(nums1), len(nums2)\n",
    "        for i in range(n1):\n",
    "            j=bisect_right(nums2, -nums1[i], key=lambda x:-x)-1\n",
    "            if j>=i:\n",
    "                break\n",
    "        else: # no break\n",
    "            return 0\n",
    "\n",
    "        ans=j-i\n",
    "        print(i,j)\n",
    "        for i in range(1, n1):\n",
    "            x=nums1[i]\n",
    "            while j<n2 and nums2[j]>=x:\n",
    "                j+=1\n",
    "            ans = max(ans, j-1-i)\n",
    "            print(i,j,nums1[i],nums2[j-1])\n",
    "            if j==n2:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        index = 0\n",
    "        for idx in range(len(nums2)):\n",
    "            while index<len(nums1) and nums1[index]>nums2[idx]:\n",
    "                index += 1\n",
    "            if index < len(nums1):\n",
    "                    ans = max(ans, idx-index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j < n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j - 1 - i > ans:\n",
    "                ans = j - i - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ret=0\n",
    "        n1,n2=len(nums1),len(nums2)\n",
    "        a,b=0,0\n",
    "        while a<n1 and b<n2:\n",
    "            while b<n2 and nums1[a]<=nums2[b]:\n",
    "                b+=1\n",
    "            ret=max(ret,b-a-1)\n",
    "            a+=1\n",
    "        return ret\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bisect(self, nums, num):\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            if nums[mid] == num:\n",
    "                return mid\n",
    "            if nums[mid] > num:\n",
    "                l = mid + 1\n",
    "            if nums[mid] < num:\n",
    "                r = mid - 1\n",
    "            \n",
    "        return l\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        j = n2 - 1\n",
    "        ret = 0\n",
    "\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                ret = max(ret, j - i)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j<n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j-i-1 > ans:\n",
    "                ans = j-i-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n, res = len(nums1), len(nums2), 0\n",
    "        for i in range(m):\n",
    "            l, r = i - 1, n\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums2[mid] >= nums1[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == i - 1: continue\n",
    "            res = max(l - i, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res=0\n",
    "        last=0\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(last,len(nums2)):\n",
    "                if nums1[i]<=nums2[j]:\n",
    "                    res=max(res,j-i)\n",
    "                else:\n",
    "                    last=j\n",
    "                    break\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        i = 0\n",
    "        distance = 0\n",
    "        for j in range(n):\n",
    "            while i < m and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < m:\n",
    "                distance = max(distance,j - i)\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j<n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j-i-1 > ans:\n",
    "                ans = j-i-1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        max_d = 0\n",
    "        i = 0\n",
    "        for j in range(len(nums2)):\n",
    "            while i < len(nums1) and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < len(nums1):\n",
    "                max_d = max(max_d, j-i)\n",
    "                \n",
    "        return max_d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for j in range(len(nums2)):\n",
    "            while i < len(nums1) and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i != len(nums1):\n",
    "                ans = max(ans, j-i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result = 0\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        for i in range(n1):\n",
    "            left, right = i, n2 - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums2[mid] >= nums1[i]):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if(right >= i):\n",
    "                result = max(result, right-i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = j = 0\n",
    "        ans = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "                if i > j:\n",
    "                  j = i\n",
    "                continue\n",
    "            else:\n",
    "                ans = max(ans, j - i)\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j<n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j-i-1 > ans:\n",
    "                ans = j-i-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        dis = 0\n",
    "        while i < len(nums1) and j < len(nums2):\n",
    "            if i <= j and nums1[i] <= nums2[j]:\n",
    "                dis = j - i\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1); n2 = len(nums2)\n",
    "        j = ans = 0\n",
    "        for i in range(n1):\n",
    "            while j < n2 and nums2[j]>= nums1[i]:\n",
    "                j += 1\n",
    "            if j - i - 1 > ans:\n",
    "                ans = j - i - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = j = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        \n",
    "        return max(j - i - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n, res = len(nums1), len(nums2), 0\n",
    "        for i in range(m):\n",
    "            if i > n: continue\n",
    "            l, r = i - 1, n\n",
    "            while l + 1 != r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums2[mid] >= nums1[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == i - 1: continue\n",
    "            res = max(l - i, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums2)\n",
    "        pre = 0\n",
    "        for i, x in enumerate(nums1):\n",
    "            left, right = min(pre, i), n \n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums2[mid] >= x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, right - i - 1)\n",
    "            pre = min(pre, right)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # nums1.reverse()\n",
    "        nums2 = nums2[::-1]\n",
    "        n = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = bisect_left(nums2, nums1[i])\n",
    "            t = (n2 - x) - i - 1\n",
    "            if t > ans:\n",
    "                ans = t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        ans = i = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                ans = max(ans, j - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        pos1, pos2 = 0,0\n",
    "        while pos1<len(nums1) and pos2<len(nums2):\n",
    "            if nums1[pos1] <= nums2[pos2]:\n",
    "                res = max(res, pos2-pos1)\n",
    "                pos2 += 1\n",
    "            else:\n",
    "                pos1 += 1\n",
    "                pos2 = max(pos2, pos1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums1)):\n",
    "            l, r = i, len(nums2) - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums2[mid] >= nums1[i]:\n",
    "                    ans = max(ans, mid - i)\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        '''\n",
    "        j一直在增加，所以一直维护一个最大距离就可以，每个数组只用遍历一次\n",
    "        '''\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        p1, p2 = 0, 0\n",
    "        while p1 < m and p2 < n:\n",
    "            while p1 < m and p2 < n and nums1[p1] <= nums2[p2] and p1 <= p2:\n",
    "                ans = max(ans, p2 - p1)\n",
    "                p2 += 1\n",
    "            else:\n",
    "                p2 += 1\n",
    "            p1 += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        j = n2 - 1\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(n1):\n",
    "            l = 0\n",
    "            r = n2 - 1\n",
    "            while (l < r) :\n",
    "                mid = l + r + 1 >> 1\n",
    "                if (nums2[mid] >= nums1[i]): l = mid\n",
    "                else: r = mid - 1\n",
    "            \n",
    "\n",
    "            if i <= l:\n",
    "                ret = max(ret, l - i)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \n",
    "        maxDistance = 0\n",
    "        index = 0\n",
    "        for j in range(len(nums2)):         \n",
    "            maxShortListIndex = min([j+1, len(nums1), len(nums2)])\n",
    "            for i in range(index, maxShortListIndex):\n",
    "                if nums1[i] > nums2[j]:\n",
    "                    index += 1\n",
    "                if nums1[i] <= nums2[j]:\n",
    "                    maxDistance = max([maxDistance, j - i]) \n",
    "                    break      \n",
    "        return maxDistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        # 从左到右遍历，nums1[i] < nums2[j]\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i = j = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return max(0, j - i - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result, m, n, nums2 = 0, len(nums1), len(nums2), nums2[::-1]\n",
    "        for i in range(min(m, n)):\n",
    "            result = max(result, n - bisect_left(nums2, nums1[i]) - 1 - i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result = 0\n",
    "        j = 0\n",
    "        for i in range(len(nums1)):\n",
    "            while j < len(nums2) and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            dis = j - i - 1\n",
    "            result = max(dis, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums2)\n",
    "        for i, x in enumerate(nums1):\n",
    "            left, right = i, n \n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums2[mid] >= x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, right - i - 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = min(len(nums2) - 1, len(nums1) - 1)\n",
    "        max_distance = 0\n",
    "        l, r = i - 1, len(nums2)\n",
    "        while i >= 0:\n",
    "            while l + 1 < r:\n",
    "                m = (l + r) // 2\n",
    "                if nums2[m] >= nums1[i]:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "            max_distance = max(max_distance, l - i)\n",
    "            i -= 1\n",
    "            l, r = i - 1, l + 1\n",
    "        return max_distance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        m=len(nums2)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            temp=nums1[i]\n",
    "            left=i\n",
    "            right=m-1\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if nums2[mid]>=temp:\n",
    "                    if mid-i>=0:\n",
    "                        ans=max(ans,mid-i)\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        tmp = nums2[::-1]\n",
    "        for i,num in enumerate(nums1):\n",
    "            index = bisect.bisect_left(tmp,num)\n",
    "            index = len(nums2)-index\n",
    "            res = max(res,index-i-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            left = i\n",
    "            right = len(nums2) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums2[mid] < nums1[i]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "                ans = max(ans, left - 1 - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        l, r = 0, 0\n",
    "        ans = 0\n",
    "        while l < m:\n",
    "            while r < n and nums1[l] <= nums2[r]:\n",
    "                r += 1\n",
    "            ans = max(ans, r - l - 1)\n",
    "            if n - l - 1<= ans:\n",
    "                break\n",
    "            l += 1\n",
    "            r = max(r, l)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result = 0\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        for i in range(n1):\n",
    "            left, right = i, n2 - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums2[mid] >= nums1[i]):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if(right >= i):\n",
    "                result = max(result, right-i)\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
